How it works
This gives a brief overview of the inner workings of MacTierra, and
therefore Tierra in general. See Ray (1981)
for a more thorough treatment.
The Tierran environment
Tierra is essentially an emulator of a parallel computer with a variable
number of CPUs. It has its own machine language (a vastly simplified
machine code with only 32 instructions) and a novel addressing mode,
both of which were designed to avoid the brittleness associated with
standard machine code. Brittleness is a problem when you wish to
allow the evolution of code fragments (which is what Tierra does), because
the vast proportion of mutant fragments are completely inviable.
Using its own machine language also prevents problems of code fragments
'escaping' and infecting the host computer, which cannot happen,
either in the original implementation, or with MacTierra.
Ray pared down traditional CISC instruction sets to end up with a language
of 32-instructions including operands, which compares favourably with
the 64 codons which are translated into the 20 amino acids used to make proteins
in real organisms.
The instructions are listed here:
nop_0 (no operation 0; used in templates)
nop_1 (no operation 1; used in templates)
or1 (flip the low bit of cx)
sh1 (shift left cx)
zero (zero cx)
if_cz (if cx=0 do next instruction)
sub_ab (subtract bx from ax, result into cx)
sub_ac (subtract cx from ax, result into ax)
inc_a (increment ax)
inc_b (increment bx)
dec_c (decrement cx)
inc_c (increment cx)
push_ax (push ax onto the stack)
push_bx (push bx onto the stack)
push_cx (push cx onto the stack)
push_dx (push dx onto the stack)
pop_ax (pop top of stack into ax)
pop_bx (pop top of stack into bx)
pop_cx (pop top of stack into cx)
pop_dx (pop top of stack into dx)
jmp (move ip to template)
jumpb (move ip backward to template)
call (call a procedure)
ret (return from procedure)
mov_cd (move cx to dx)
mov_ab (move ax to bx)
mov_iab (move instruction pointed to by bx to address in ax)
adr (address of nearest template into ax)
adrb (search backwards for template)
adrf (search forwards for template)
mal (allocate memory for daughter cell)
divide (cell division)
The Tierra language uses 'addressing by template', another feature borrowed
from the world of wet life. After each jmp or adr instruction
is expected a template of perhaps 4 instructions which consists of nop_0
and nop_1 instuctions. On execution of a jmp the simulator
looks either forwards or backwards from the instruction pointer for the complement
of this template, and resumes execution at this point. Thus a mutation
in a template which turns 0001 to 0011 could have signficant consequences on
program execution.
Each creature in the soup consists simply of a string of machine instructions, but
is assigned by the simulator its own processor (CPU) which executes those instructions,
in the standard fetch-decode-execute-increment IP cycle of most computers. For
example, if the instruction pointed to by the IP is 0x02 (or1), the CPU flips the
low-order bit of the contents of register cx. If it is 0x14 (jmp), the
CPU looks in both directions for the complement of the 4 instructions that follow
that jmp instruction, and then moves the IP to point to that if found.
However, execution of these instructions is flawed at a low frequency, and the
copying of instructions from parent to offspring also involves flaws at a low
rate. This is equivalent to mutation and copying errors during DNA repliation.
The CPU data stucture is:
struct cpu {
short ax; //Address register
short bx; //Address register
short cx; //Numerical register
short dx; //Numerical register
char fl; //Flag (set when errors occur)
char sp; //Stack pointer
short st[10]; //Stack
short ip; //Instruction pointer
}
The soup is simply a block of computer memory between 16 and 256 kilobytes in size,
within which the creatures live. It is cellular, in the sense that a creature
cannot simply write instructions anywhere, but has only write priviledges in
its own block, and that of its daugher cell, if it has one (though see Settings for
details of how this can be controlled).
In MacTierra, the soup is simply copied into a pixel map for display, and can
then be overlayed with a 'blocks' or 'fecundity' layer, to show more detail
about the location of active creatures.
The slicer doles out to each creature in turn a short time-slice, during which it executes
a small number of instructions. This time-slicing enables an imperfect implementation
of parallelism in the simulator. In MacTierra, the slicer is implemented as a
circular list of creatures which is rotated at every time-slice. Offspring creatures
are only inserted into the slicer queue when they become independent from their
parent (when the parent executes the divide instruction).
When a creature is born, it is entered into a linear 'reaper' queue, at the bottom.
Put simply, it moves up the queue when it fails to execute instructions (because its
algorithm is flawed), and stays where it is, or moves down when it
succeeds. So flawed algorithms tend to move up the queue. When the soup
reaches the reaping threshold, say 80% full of creatures, the
reaper kicks in, and kills off the creature which is at the top of the
reaper queue (i.e. the most flawed one), at which point the CPU is deallocated,
and the creature is removed from the soup (though its dead code remains there).
When a creature is born, it may have a genotype that differs from its parent
because of mutations and copying errors. In MacTierra, such a new genotype is
distinguished from its parent by a '; for example, a creature called 80aaa' has
a different genotype from 80aaa, from which it is descended.
Many such offspring will be inviable, and will be quickly eliminated from the soup.
However, when a new genotype managed to successfully replicate twice (i.e. produce
two offspring which are identical to itself), then it is entered into the genebank,
and assigned a new genotype. So 80aaa' may give rise to 80aab.
Genotypes are named using a combination of their length (80) and a three-letter
code that is simply incremented when a new creature enters the genebank (aab).
Mutations introduce variabilty into the system, and it is replication with
variabilty that is necessary for evolution to occur. In MacTierra, variation is
introduced in three ways: in cosmic mutations,
copying errors, and flawed instruction execution.
Cosmic mutations cause the flipping of
random bits in the soup at a low frequency, and are responsible for the 'speckles'
you can see in a young MacTierra soup.
Copy errors occur during execution of the
mov_iab instruction, and result in the instruction being copied changing
at a low rate.
Flaws can occur during execution of the any instruction, and result in the instruction
either using the wrong registers, or doing an operation one too many or too few times.
What to look for
Tierra provides a very rich environment in which all sorts of ecological, evolutionary
and informational patterns can be observed. MacTierra in particular is extremely
amenable to experimentation, by interaction of the user with running simulations.
Some things to look for, and some ideas for experiments you can perform are:
- Long-term trends
- Does maximum fitness increase over time?
- How does the number of coexisting species vary over time? How is this
affected by the size of the soup?
- How do speciation and extinction rates vary over time? Does MacTierra
show 'punctuated equilibria' in evolution? i.e. long periods of fairly low
activity, interspersed with bursts of high speciation and extinction. Are
the two rates correlated?
- Different strategies for replication
- Do parasites evolve?
You get an idea of whether an organism is a parasite by
seeing if it replicates on its own. Dragging the suspected parasite
into an empty soup (hold down the option key when choosing 'New' on the File
menu), then run to see if it replicates. If not, is some dead code in the soup
sufficient to get it going? Drag another creature (say 80aaa) from the Menagerie
into the soup, close to the parasite, then delete it by dragging to the trash; this
leaves the 'dead code' behind. Now run again.
- Does any form of sociality arise? Some creatures may need to occur in large
groups before they can replicate effectively.
- Interactions between creatures
- You can track the populations of two creatures by dragging them into the
two wells in the graph window, and collecting 'Two genotype' stats for plotting.
Do you get Lotka-Volterra dynamics?
- Results of different levels of mutation
- What happens when mutation is really high? Or really low? Does this
affect speciation and extinction rates, and maximum fitness?
- Results of selection for creature size.
- How does creature size respond to selection on size? How does this
interact with mutation rates?
- That should be enough to keep you busy ;-)
If you evolve any neat creatures, or have ideas for other interesting experiments
that could be performed, mail me!
